{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3adf6cca",
   "metadata": {},
   "source": [
    "可以在[Bookshop.org](https://bookshop.org/a/98697/9781098155438) 和\n",
    "[Amazon](https://www.amazon.com/_/dp/1098155432?smid=ATVPDKIKX0DER&_encoding=UTF8&tag=oreilly20-20&_encoding=UTF8&tag=greenteapre01-20&linkCode=ur2&linkId=e2a529f94920295d27ec8a06e757dc7c&camp=1789&creative=9325)获取纸制版和电子版的*Think Python 3e*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "6c6265de",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from os.path import basename, exists\n",
    "\n",
    "def download(url):\n",
    "    filename = basename(url)\n",
    "    if not exists(filename):\n",
    "        from urllib.request import urlretrieve\n",
    "\n",
    "        local, _ = urlretrieve(url, filename)\n",
    "        print(\"Downloaded \" + str(local))\n",
    "    return filename\n",
    "\n",
    "download('https://gitee.com/regentsai/Think_Python_3e_CN/blob/master/thinkpython.py');\n",
    "download('https://gitee.com/regentsai/Think_Python_3e_CN/blob/master/diagram.py');\n",
    "\n",
    "import thinkpython"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "59a8621b",
   "metadata": {},
   "source": [
    "# 第12章:文本分析和生成\n",
    "\n",
    "截止目前我们已经介绍了Python的核心数据类型：列表，字典，元组以及使用它们的一些算法。本章我们将使用它们探索文本分析和马尔科夫Markov生成：\n",
    "\n",
    "- 文本分析是一种描述文档中单词之间统计学关系的方法，比如一个单词在另一个之后的概率;\n",
    "- 马尔科夫生成是一种生成与源文本类似的后续单词与短语的过程。\n",
    "\n",
    "这些算法与大语言模型(Large Language Model， LLM)的部分模块类似，是聊天机器人的关键组件。\n",
    "\n",
    "我们首先计算一本书中每个单词的出现次数。然后我们将查看成对的单词，创建能在其他单词之后的单词列表。我们将创建一个马尔科夫生成器。作为练习，你有机会创建一个更通用的版本。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e3811b8",
   "metadata": {},
   "source": [
    "## 唯一的单词\n",
    "\n",
    "作为文本分析的第1步，让我们阅读Robert Louis Stevenson的书籍《化身博士 The Strange Case Of Dr. Jekyll And Mr. Hyde》，计算唯一单词的数量。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6567e1bf",
   "metadata": {
    "tags": []
   },
   "source": [
    "以下单元格从古登堡计划下载该书："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "4cd1c980",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "download('https://www.gutenberg.org/cache/epub/43/pg43.txt');"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5465ab1d",
   "metadata": {
    "tags": []
   },
   "source": [
    "使用第8章的`clean_file`函数，移除古登堡的额外信息，将只包含书籍正文的内容写入“干净clean”的文件中。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "52ebfe94",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def is_special_line(line):\n",
    "    return line.strip().startswith('*** ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "49cfc352",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def clean_file(input_file, output_file):\n",
    "    reader = open(input_file, encoding='utf-8')\n",
    "    writer = open(output_file, 'w')\n",
    "\n",
    "    for line in reader:\n",
    "        if is_special_line(line):\n",
    "            break\n",
    "\n",
    "    for line in reader:\n",
    "        if is_special_line(line):\n",
    "            break\n",
    "        writer.write(line)\n",
    "        \n",
    "    reader.close()\n",
    "    writer.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "44e53ce6",
   "metadata": {},
   "outputs": [],
   "source": [
    "filename = 'dr_jekyll.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "50d1fafa",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "clean_file('pg43.txt', filename)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bc66d7e2",
   "metadata": {},
   "source": [
    "我们将使用`for`循环从文件中读取行，使用`split`将行分隔为单词。然后，要追踪唯一的单词，我们将每个单词存储为字典的键。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "16d24028",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6040"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "unique_words = {}\n",
    "for line in open(filename):\n",
    "    seq = line.split()\n",
    "    for word in seq:\n",
    "        unique_words[word] = 1\n",
    "\n",
    "len(unique_words)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "85171a3a",
   "metadata": {},
   "source": [
    "字典的长度是唯一的单词数量，大约6000个。但如果我们检查它们，有些并不是有效的单词。\n",
    "\n",
    "例如，让我们寻找`unique_words`中的最长单词。我们可以使用`sorted`进行排序，将`len`函数作为key关键字参数的值，让单词按长度排序。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "1668e6bd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['chocolate-coloured',\n",
       " 'superiors—behold!”',\n",
       " 'coolness—frightened',\n",
       " 'gentleman—something',\n",
       " 'pocket-handkerchief.']"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(unique_words, key=len)[-5:]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "795f5327",
   "metadata": {},
   "source": [
    "切片`[-5:]`选取被排序的列表中的最后5个元素，是最长的单词。\n",
    "\n",
    "\n",
    "列表包含实际很长的单词，比如\"circumscription\"，有些是连字词，比如\"chocolate-coloured\"。但有些最长的“单词”实际是由横线分隔的两个单词。其他单词包含标点符号，比如句号，感叹号，问号。\n",
    "\n",
    "所以，在我们继续之前，先处理横线和其他标点符号。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf89fafa",
   "metadata": {},
   "source": [
    "## 标点符号\n",
    "\n",
    "要分辨文本中的单词，我们需要处理两个问题：\n",
    "\n",
    "- 当横线出现在一行中，我们需要用空格替换横线，然后使用`split`将单词分开;\n",
    "- 分割之后，我们可以使用`strip`移除标点符号。\n",
    "\n",
    "要处理第1个问题，我们可以使用以下函数，接受一个字符串，替换横线为空格，分割字符串，返回结果列表。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "ed5f0a43",
   "metadata": {},
   "outputs": [],
   "source": [
    "def split_line(line):\n",
    "    return line.replace('—', ' ').split()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5decdec",
   "metadata": {},
   "source": [
    "注意`split_line`只替换横线，不替换连字符。以下是函数的示例：\n",
    "\n",
    "译注：连字符是半角的减号对应字符，横线是全角的破折线符号，两个字符是`-,—`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "a9df2aeb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['coolness', 'frightened']"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "split_line('coolness—frightened')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "5a10e967",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['chocolate-coloured']"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "split_line('chocolate-coloured')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d9eb318",
   "metadata": {},
   "source": [
    "现在，要移除每个单词首尾的标点符号，我们可以使用`strip`函数，但我们需要一个被认为是标点的字符串列表。\n",
    "\n",
    "Python字符串中的字符是Unicode编码，一种几乎能表示任何字符的国际标准。`unicodedata`模块提供`category`函数，可以用于分辨哪些字符串是标点。给定一个字符，将返回该字符所属的分类。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "b138b123",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Lu'"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import unicodedata\n",
    "\n",
    "unicodedata.category('A')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "994835ea",
   "metadata": {},
   "source": [
    "`'A'`的分类是`'Lu'`，`'L'`表示它是一个字母letter,`'u'`表示它是大写的。\n",
    "\n",
    "`'.'`的分类是`'Po'`，`'P'`表示它是一个标点符号punctuation，`'o'`表示它属于其他\"other\"类别。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "fe65df44",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Po'"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "unicodedata.category('.')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "03773b9b",
   "metadata": {},
   "source": [
    "我们可以通过检查字符的分类是否以`'P'`开始，来判断它是否是标点符号。以下循环将书中的唯一标点符号存储进字典中。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "b47a87cf",
   "metadata": {},
   "outputs": [],
   "source": [
    "punc_marks = {}\n",
    "for line in open(filename):\n",
    "    for char in line:\n",
    "        category = unicodedata.category(char)\n",
    "        if category.startswith('P'):\n",
    "            punc_marks[char] = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e6741dfa",
   "metadata": {},
   "source": [
    "要得到一组标点符号，我们可以将字典中的键合并为字符串。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "348949be",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ".’;,-“”:?—‘!()_\n"
     ]
    }
   ],
   "source": [
    "punctuation = ''.join(punc_marks)\n",
    "print(punctuation)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6af8d5a2",
   "metadata": {},
   "source": [
    "现在我们知道了哪些字符是标点，就可以编写程序，接受一个单词，清除首尾的标点符号，并将其转化为小写。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "06121901",
   "metadata": {},
   "outputs": [],
   "source": [
    "def clean_word(word):\n",
    "    return word.strip(punctuation).lower()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58a78cb1",
   "metadata": {},
   "source": [
    "以下是示例："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "881ed9f8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'behold'"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clean_word('“Behold!”')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "314e4fbd",
   "metadata": {},
   "source": [
    "由于`strip`移除的是首尾的字符，它会保留连字词。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "ab5d2fed",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'pocket-handkerchief'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clean_word('pocket-handkerchief')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99050f8a",
   "metadata": {},
   "source": [
    "以下是使用`split_line`和`clean_word`识别书中唯一单词的循环。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "2fdfb936",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4005"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "unique_words2 = {}\n",
    "for line in open(filename):\n",
    "    for word in split_line(line):\n",
    "        word = clean_word(word)\n",
    "        unique_words2[word] = 1\n",
    "\n",
    "len(unique_words2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "992e5466",
   "metadata": {},
   "source": [
    "在这个严格定义下，有大约4000个唯一的单词。我们也可以确认被清洗后的最长单词。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "3104d191",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['circumscription',\n",
       " 'unimpressionable',\n",
       " 'fellow-creatures',\n",
       " 'chocolate-coloured',\n",
       " 'pocket-handkerchief']"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(unique_words2, key=len)[-5:]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8014c330",
   "metadata": {},
   "source": [
    "现在让我们看看每个单词用了多少次。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7ef40180",
   "metadata": {},
   "source": [
    "## 单词频次\n",
    "\n",
    "以下循环计算每个唯一单词的频次。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "4fba7d1c",
   "metadata": {},
   "outputs": [],
   "source": [
    "word_counter = {}\n",
    "for line in open(filename):\n",
    "    for word in split_line(line):\n",
    "        word = clean_word(word)\n",
    "        if word not in word_counter:\n",
    "            word_counter[word] = 1\n",
    "        else:\n",
    "            word_counter[word] += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bd680b81",
   "metadata": {},
   "source": [
    "我们第1次看到一个单词，将它的频次为`1`。如果我们再次看到该单词，增加它的频次。\n",
    "\n",
    "要查看哪些单词出现的最多。我们可以使用`items`获得`word_counter`的键值对，并按值（频次）进行排序。\n",
    "\n",
    "首先我们定义函数，选择键值对中的第2个元素（频次）。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "4be34c95",
   "metadata": {},
   "outputs": [],
   "source": [
    "def second_element(t):\n",
    "    return t[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b15a5bd6",
   "metadata": {},
   "source": [
    "现在我们可以使用`sorted`，提供两个关键字参数：\n",
    "\n",
    "- `key=second_element`表示按频次进行排序\n",
    "- `reverse=True`表示这些项应该按倒序排列，即频次最高的在前面。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "8efe7c4c",
   "metadata": {},
   "outputs": [],
   "source": [
    "items = sorted(word_counter.items(), key=second_element, reverse=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "db6812e2",
   "metadata": {},
   "source": [
    "以下是频次最高的5个单词："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "79c17341",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1614\tthe\n",
      "972\tand\n",
      "941\tof\n",
      "640\tto\n",
      "640\ti\n"
     ]
    }
   ],
   "source": [
    "for word, freq in items[:5]:\n",
    "    print(freq, word, sep='\\t')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "551e81bb",
   "metadata": {},
   "source": [
    "在下一节，我们将这个循环封装进函数中。我们也会使用一个新特性：可选形参。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45243ccc",
   "metadata": {},
   "source": [
    "## 可选形参\n",
    "\n",
    "我们已经使用过接受可选形参的内建函数。例如，`round`接受可选形参`ndigits`，表示要近似到小数点后多少位。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "838bcb4f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.142"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "round(3.141592653589793, ndigits=3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6ae60945",
   "metadata": {},
   "source": [
    "但并非只有内建函数可以这样，我们可以自行编写有可选形参的函数。例如，以下函数接受两个形参，`word_counter`和`num`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "90c45e7e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_most_common(word_counter, num=5):\n",
    "    items = sorted(word_counter.items(), key=second_element, reverse=True)\n",
    "\n",
    "    for word, freq in items[:num]:\n",
    "        print(freq, word, sep='\\t')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78cb1531",
   "metadata": {},
   "source": [
    "第2个参数看起来像一个赋值语句，但实际上并不是，它是一个可选形参。\n",
    "\n",
    "如果你调用该函数，提供一个实参，`num`将获得**默认值default value** `5`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "e106be95",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1614\tthe\n",
      "972\tand\n",
      "941\tof\n",
      "640\tto\n",
      "640\ti\n"
     ]
    }
   ],
   "source": [
    "print_most_common(word_counter)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "29753ad6",
   "metadata": {},
   "source": [
    "如果你调用该函数，提供两个实参，则将第2个实参赋值给`num`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "8101a510",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1614\tthe\n",
      "972\tand\n",
      "941\tof\n"
     ]
    }
   ],
   "source": [
    "print_most_common(word_counter, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9bf907b",
   "metadata": {},
   "source": [
    "在这个例子里，我们会说可选的实参**覆盖overrides**了默认值。\n",
    "\n",
    "如果函数同时有必须形参和可选形参，函数头中的必须形参必须在前面，然后是可选形参。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "c046117b",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "non-default argument follows default argument (3116647453.py, line 1)",
     "output_type": "error",
     "traceback": [
      "  \u001b[36mCell\u001b[39m\u001b[36m \u001b[39m\u001b[32mIn[29]\u001b[39m\u001b[32m, line 1\u001b[39m\n\u001b[31m    \u001b[39m\u001b[31mdef bad_function(n=5, word_counter):\u001b[39m\n                          ^\n\u001b[31mSyntaxError\u001b[39m\u001b[31m:\u001b[39m non-default argument follows default argument\n"
     ]
    }
   ],
   "source": [
    "%%expect SyntaxError\n",
    "\n",
    "def bad_function(n=5, word_counter):\n",
    "    return None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f450df2",
   "metadata": {
    "tags": []
   },
   "source": [
    "## 字典减法\n",
    "\n",
    "假设我们想要对书籍进行拼写检查，寻找可能被错误拼写的单词列表。一种方式是寻找书中出现，但不在有效单词列表中的单词。在先前的章节，我们已经使用字谜中有效的单词列表。现在我们使用这个列表对《化身博士》拼写检查。\n",
    "\n",
    "我们可以将这个问题看作集合减法，我们想要找出一个集合中所有的单词（书中的所有单词），它们不在另一个集合（字谜列表中的单词）中。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a3804d82",
   "metadata": {
    "tags": []
   },
   "source": [
    "以下单元格会下载单词列表。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "edd8ff1c",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "download('https://gitee.com/regentsai/Think_Python_3e_CN/blob/master/words.txt');"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a46556c",
   "metadata": {},
   "source": [
    "与之前一样，我们可以读取`words.txt`的内容，将其分割为字符串的列表。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "67ef3e08",
   "metadata": {},
   "outputs": [],
   "source": [
    "word_list = open('words.txt').read().split()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22becbab",
   "metadata": {},
   "source": [
    "然后我们将这些单词存储为字典的键，以便使用`in`运算符，快速检查单词是否有效。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "471d58e9",
   "metadata": {},
   "outputs": [],
   "source": [
    "valid_words = {}\n",
    "for word in word_list:\n",
    "    valid_words[word] = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "94cc7c61",
   "metadata": {},
   "source": [
    "现在，要识别出现在书中但不在单词列表中的单词，我们使用`subtract`函数，接受两个字典作为形参，返回这两个字典的“差集”。\n",
    "\n",
    "译注：Python中的集合`set`类型支持用`-`求差集。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "4d4c3538",
   "metadata": {},
   "outputs": [],
   "source": [
    "def subtract(d1, d2):\n",
    "    res = {}\n",
    "    for key in d1:\n",
    "        if key not in d2:\n",
    "            res[key] = d1[key]\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e70c63b4",
   "metadata": {},
   "source": [
    "以下是使用该函数的示例："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "8b42e014",
   "metadata": {},
   "outputs": [],
   "source": [
    "diff = subtract(word_counter, valid_words)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f8ada7bd",
   "metadata": {},
   "source": [
    "要获得可能错误拼写的单词，我们可以打印`diff`中最常见的单词。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "f48be152",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "640\ti\n",
      "628\ta\n",
      "128\tutterson\n",
      "124\tmr\n",
      "98\thyde\n"
     ]
    }
   ],
   "source": [
    "print_most_common(diff)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "deeec418",
   "metadata": {},
   "source": [
    "最常见的“错误拼写”的单词基本是人名和单字母单词（Utterson是主角的朋友）。\n",
    "\n",
    "如果我们选择只出现一次的单词，它们通常确实是错误拼写的单词。我们可以遍历字典的项，创建出现频次为1的单词列表。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "5716f967",
   "metadata": {},
   "outputs": [],
   "source": [
    "singletons = []\n",
    "for word, freq in diff.items():\n",
    "    if freq == 1:\n",
    "        singletons.append(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "98ae9281",
   "metadata": {},
   "source": [
    "以下是一些示例单词："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "b37219f5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['gesticulated', 'abjection', 'circumscription', 'reindue', 'fearstruck']"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "singletons[-5:]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c5040834",
   "metadata": {},
   "source": [
    "多数也是有效的单词，但`'reindue'`应该是`'reinduce'`的错误拼写。所以我们至少发现了一个错误。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "afcbbe19",
   "metadata": {},
   "source": [
    "## 随机数\n",
    "\n",
    "作为马尔科夫文本生成的一部分，我们将从`word_counter`中随机选取一组单词。\n",
    "\n",
    "但首先让我们讨论下随机性。\n",
    "\n",
    "对于相同的输入，多数计算机程序是**确定的deterministic**，每次生成相同的输出。然而对于某些应用，我们想要让计算机不可预测，游戏是一个例子，但有更多应用需要随机性。\n",
    "\n",
    "创建一个真随机的程序是困难的，但有方法来模拟。可以使用生成**伪随机pseudorandom**数的算法。伪随机数不是真随机的，它们由确定的计算生成，但简单看这些数字是无法区分它们是否随机的。\n",
    "\n",
    "`random`模块提供生成伪随机数的函数，我们可以像这样导入："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "75b548a9",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "2bfa31ae",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# 这个单元格初始化随机数生成器，让这个笔记每次产生相同的随机数序列\n",
    "\n",
    "random.seed(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8cbbd7f8",
   "metadata": {},
   "source": [
    "`random`模块提供函数`choice`，从一个序列中随机抽取一个元素，每个元素被抽取的概率相等。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "6f5d5c1c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t = [1, 2, 3]\n",
    "random.choice(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57c15af2",
   "metadata": {},
   "source": [
    "如果你再次调用函数，你可能会获得相同的元素，也可能获得不同的元素。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "1445068b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random.choice(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f0c2572",
   "metadata": {},
   "source": [
    "多次运行后我们获得每个元素的次数应该大致相等。\n",
    "\n",
    "如果你对字典使用`choice`，将产生`KeyError`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "4fc47ecd",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "ename": "KeyError",
     "evalue": "422",
     "output_type": "error",
     "traceback": [
      "\u001b[31mKeyError\u001b[39m\u001b[31m:\u001b[39m 422\n"
     ]
    }
   ],
   "source": [
    "%%expect KeyError\n",
    "\n",
    "random.choice(word_counter)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "592722f3",
   "metadata": {},
   "source": [
    "要选择一个随机的键，你必须将键放在列表中，然后调用`choice`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "91ae9d4c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'posture'"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "words = list(word_counter)\n",
    "random.choice(words)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "172d72f6",
   "metadata": {},
   "source": [
    "如果我们生成单词的随机序列，它不会有意义。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "8bf595c1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "listen relieved apocryphal nor busy spoke "
     ]
    }
   ],
   "source": [
    "for i in range(6):\n",
    "    word = random.choice(words)\n",
    "    print(word, end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0e2fbc4",
   "metadata": {},
   "source": [
    "部分问题在于，我们没有考虑有些单词比其他单词更常用。如果我们以不同的“权重”选取单词，有些单词选取更多次，结果应该会更好。\n",
    "\n",
    "如果我们使用`word_counter`中的值作为权重，每个单词将根据它们的频次被选取。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "22953b65",
   "metadata": {},
   "outputs": [],
   "source": [
    "weights = word_counter.values()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5098bf93",
   "metadata": {},
   "source": [
    "`choices`函数接受权重`weights`作为可选参数。\n",
    "\n",
    "译注：`weights`应该是一个有序的可迭代对象。一般字典和集合都是无序的数据结构，但Python的字典从3.6版本开始会记录键值对插入的顺序，3.7版本正式纳入语言规范。将`dict.items(),dict.keys(),dict.values()`视作有序的对象通常是安全的，但显式使用`dict.items()`进行成对迭代可能更安全，或者使用标准库中的有序字典数据结构`collections.OrderedDict`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "1c7cdf4d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['than']"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random.choices(words, weights=weights)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a3341e84",
   "metadata": {},
   "source": [
    "`choices`还接受另一个可选参数`k`，指定选取多少个单词。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "a7a3aa42",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['reach', 'streets', 'disappearance', 'a', 'said', 'to']"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random_words = random.choices(words, weights=weights, k=6)\n",
    "random_words"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e57e6f3d",
   "metadata": {},
   "source": [
    "结果是一个字符串的列表，我们可以用空格进行合并，让它更像一个句子。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "c4286fb3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'reach streets disappearance a said to'"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "' '.join(random_words)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c7a35dff",
   "metadata": {},
   "source": [
    "如果你从书中随机选取单词，你能对使用的词汇倾向有一定的了解，但一组随机的单词不太可能有意义，它们与后续的单词没有联系。\n",
    "\n",
    "例如，在真实的句子中，你希望冠词后面跟着形容词或者名词，但不太可能跟着动词或副词。\n",
    "\n",
    "所以下一步是找到这些单词之间的联系。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0921dd53",
   "metadata": {},
   "source": [
    "## 双词组\n",
    "\n",
    "我们不再每次获取一个单词，而是查看两个单词的序列，称为**双词组bigrams**。三个单词的序列称为**三词组trigram**，不确定的单词序列称为**n词组 n-gram**。\n",
    "\n",
    "现在让我们编写程序，寻找书中所有的双词组，以及每个双词组出现的次数。要存储结果，我们使用字典，满足：\n",
    "\n",
    "- 键是表示双词组的字符串元组，\n",
    "- 值是表示频次的整数\n",
    "\n",
    "该字典名为`bigram_counter`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "d8ee02f6",
   "metadata": {},
   "outputs": [],
   "source": [
    "bigram_counter = {}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "33f97a2a",
   "metadata": {},
   "source": [
    "以下函数接受两个字符串组成的列表，转化为对应的字符串元组，可以作为字典的键。然后如果`bigram_counter`中不存在于就将其添加为键，存在则将频次加1。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "bfdb1de1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_bigram(bigram):\n",
    "    key = tuple(bigram)\n",
    "    if key not in bigram_counter:\n",
    "        bigram_counter[key] = 1\n",
    "    else:\n",
    "        bigram_counter[key] += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5c30f429",
   "metadata": {},
   "source": [
    "当我们遍历全书时，我们必须追踪每个连续的单词对。所以如果我们看到序列\"man is not truly one\", 我们要添加的双词组是\"man is\", \"is not\", \"not truly\", 和\"truly one\"。\n",
    "\n",
    "要追踪这些双词组，我们将使用名为`window`的列表，因为它像一个划过书籍每一行的窗口，每次只展示两个单词。刚开始时，`window`为空列表。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "2e73df79",
   "metadata": {},
   "outputs": [],
   "source": [
    "window = []"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9376558c",
   "metadata": {},
   "source": [
    "我们将使用以下函数处理单词，一次一个。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "495ad429",
   "metadata": {},
   "outputs": [],
   "source": [
    "def process_word(word):\n",
    "    window.append(word)\n",
    "    \n",
    "    if len(window) == 2:\n",
    "        count_bigram(window)\n",
    "        window.pop(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56895591",
   "metadata": {},
   "source": [
    "第一次调用函数时，将给定单词追加到`window`中。由于窗口中只有1个单词，我们还没有双词组，所以函数结束。\n",
    "\n",
    "第2次调用函数时（以及后面的每次），它追加第2个单词到`window`中。由于窗口中有两个单词，它调用`count_bigram`以追踪每个双词组出现的次数。然后它使用`pop`从窗口中移除第1个单词。\n",
    "\n",
    "以下程序遍历书中的单词，然后一次处理一个："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "c1224061",
   "metadata": {},
   "outputs": [],
   "source": [
    "for line in open(filename):\n",
    "    for word in split_line(line):\n",
    "        word = clean_word(word)\n",
    "        process_word(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "20c4627a",
   "metadata": {},
   "source": [
    "结果是一个字典，映射每个双词组出现的次数。我们可以使用`print_most_common`查看最常见的双词组。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "4296485a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "178\t('of', 'the')\n",
      "139\t('in', 'the')\n",
      "94\t('it', 'was')\n",
      "80\t('and', 'the')\n",
      "73\t('to', 'the')\n"
     ]
    }
   ],
   "source": [
    "print_most_common(bigram_counter)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "757bd309",
   "metadata": {},
   "source": [
    "查看这些结果，我们可以了解哪些单词对是最有可能在一起的。我们也可以像这样使用结果生成随机文本："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "e03fd803",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "random.seed(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "f6ee1840",
   "metadata": {},
   "outputs": [],
   "source": [
    "bigrams = list(bigram_counter)\n",
    "weights = bigram_counter.values()\n",
    "random_bigrams = random.choices(bigrams, weights=weights, k=6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eda80407",
   "metadata": {},
   "source": [
    "`bigrams`是本书中出现的双词组列表，`weights`是每个双词组的频次，因此`random_bigrams`是按照频率选取双词组的采样。\n",
    "\n",
    "以下是结果："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "d6c65d79",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "to suggest this preface to detain fact is above all the laboratory "
     ]
    }
   ],
   "source": [
    "for pair in random_bigrams:\n",
    "    print(' '.join(pair), end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f24c3b6",
   "metadata": {},
   "source": [
    "这种方式比随机选取单词更好，但句子依然不是很合理。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a13d93b5",
   "metadata": {},
   "source": [
    "## 马尔科夫分析\n",
    "\n",
    "我们可以用马尔科夫文本分析来更好的处理。它会计算文本中每个单词的后续单词列表。例如，我们将分析*Eric, the Half a Bee*中的歌词："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "3171d592",
   "metadata": {},
   "outputs": [],
   "source": [
    "song = \"\"\"\n",
    "Half a bee, philosophically,\n",
    "Must, ipso facto, half not be.\n",
    "But half the bee has got to be\n",
    "Vis a vis, its entity. D'you see?\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "583ab9f0",
   "metadata": {},
   "source": [
    "要存储结果，我们将使用字典映射每个单词到跟随它的单词列表。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "3321e6a4",
   "metadata": {},
   "outputs": [],
   "source": [
    "successor_map = {}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5d85b09",
   "metadata": {},
   "source": [
    "例如，让我们开始处理歌中的前2个单词。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "e4e55c71",
   "metadata": {},
   "outputs": [],
   "source": [
    "first = 'half'\n",
    "second = 'a'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0349fe78",
   "metadata": {},
   "source": [
    "如果第1个单词不在`successor_map`中，我们将其作为键，对应的值是包含第2个单词的列表。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "f25dcb5e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'half': ['a']}"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "successor_map[first] = [second]\n",
    "successor_map"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "55bb8df9",
   "metadata": {},
   "source": [
    "如果第1个单词中已经在字典中了，我们可以用它找到已知的后续单词列表，将新的后续单词追加到其中。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "990354a0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'half': ['a', 'not']}"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "first = 'half'\n",
    "second = 'not'\n",
    "\n",
    "successor_map[first].append(second)\n",
    "successor_map"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6289cc32",
   "metadata": {},
   "source": [
    "以下函数封装了这些步骤。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "b9371452",
   "metadata": {},
   "outputs": [],
   "source": [
    "def add_bigram(bigram):\n",
    "    first, second = bigram\n",
    "    \n",
    "    if first not in successor_map:\n",
    "        successor_map[first] = [second]\n",
    "    else:\n",
    "        successor_map[first].append(second)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "74a51700",
   "metadata": {},
   "source": [
    "如果相同的双词组出现过多次，第2个单词会在列表中出现多次。通过这种方式，`successor_map`追踪了每个后续单词出现的次数。\n",
    "\n",
    "我们再次使用列表`window`存储成对的连续单词。我们将使用以下函数处理单词，一次一个。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "8c3f45c2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def process_word_bigram(word):\n",
    "    window.append(word)\n",
    "    \n",
    "    if len(window) == 2:\n",
    "        add_bigram(window)\n",
    "        window.pop(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "861a60d9",
   "metadata": {},
   "source": [
    "以下是处理歌词中单词的过程："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "641990a3",
   "metadata": {},
   "outputs": [],
   "source": [
    "successor_map = {}\n",
    "window = []\n",
    "\n",
    "for word in song.split():\n",
    "    word = clean_word(word)\n",
    "    process_word_bigram(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf490d67",
   "metadata": {},
   "source": [
    "以下是结果："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "9322a49a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'half': ['a', 'not', 'the'],\n",
       " 'a': ['bee', 'vis'],\n",
       " 'bee': ['philosophically', 'has'],\n",
       " 'philosophically': ['must'],\n",
       " 'must': ['ipso'],\n",
       " 'ipso': ['facto'],\n",
       " 'facto': ['half'],\n",
       " 'not': ['be'],\n",
       " 'be': ['but', 'vis'],\n",
       " 'but': ['half'],\n",
       " 'the': ['bee'],\n",
       " 'has': ['got'],\n",
       " 'got': ['to'],\n",
       " 'to': ['be'],\n",
       " 'vis': ['a', 'its'],\n",
       " 'its': ['entity'],\n",
       " 'entity': [\"d'you\"],\n",
       " \"d'you\": ['see']}"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "successor_map"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ff7bad74",
   "metadata": {},
   "source": [
    "单词`'half'`的后面可以跟随`'a'`, `'not'`或者`'the'`。`'a'`的后面可以跟随`'bee'`或`'vis'`。其他多数单词只出现1次，因此它们后面只会跟随1个单词。\n",
    "\n",
    "现在让我们分析书籍："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "45a60c52",
   "metadata": {},
   "outputs": [],
   "source": [
    "successor_map = {}\n",
    "window = []\n",
    "\n",
    "for line in open(filename):\n",
    "    for word in split_line(line):\n",
    "        word = clean_word(word)\n",
    "        process_word_bigram(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2676e2fb",
   "metadata": {},
   "source": [
    "我们可以看看任意单词后面可以跟随的单词。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "3e86102c",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "story ['of', 'of', 'indeed', 'but', 'for', 'of', 'that']\n",
      "incident ['of', 'of', 'at', 'of', 'of', 'at', 'this']\n",
      "lanyon’s ['narrative', 'there', 'face', 'manner', 'narrative', 'the', 'condemnation']\n",
      "common ['it', 'interest', 'friends', 'friends', 'observers', 'but', 'quarry']\n",
      "relief ['the', 'to', 'when', 'that', 'that', 'of', 'it']\n",
      "appearance ['of', 'well', 'something', 'he', 'amply', 'of', 'which']\n",
      "going ['east', 'in', 'to', 'to', 'up', 'to', 'of']\n",
      "till ['at', 'the', 'i', 'yesterday', 'the', 'that', 'weariness']\n",
      "walk ['and', 'into', 'with', 'all', 'steadfastly', 'attired', 'with']\n",
      "sounds ['nothing', 'carried', 'out', 'the', 'of', 'of', 'with']\n",
      "really ['like', 'damnable', 'can', 'a', 'a', 'not', 'be']\n",
      "does ['not', 'not', 'indeed', 'not', 'the', 'not', 'not']\n",
      "reply ['i', 'but', 'whose', 'i', 'some', 'that’s', 'i']\n",
      "continued ['mr', 'the', 'the', 'the', 'the', 'poole', 'utterson']\n",
      "seems ['scarcely', 'hardly', 'to', 'she', 'much', 'he', 'to']\n",
      "walked ['on', 'over', 'some', 'was', 'on', 'with', 'fast']\n",
      "that’s ['a', 'it', 'talking', 'very', 'not', 'such', 'not']\n",
      "although ['i', 'a', 'it', 'the', 'we', 'they', 'i']\n",
      "until ['the', 'the', 'they', 'they', 'the', 'to-morrow', 'i']\n",
      "disappearance ['or', 'the', 'of', 'of', 'here', 'and', 'but']\n",
      "step ['into', 'or', 'back', 'natural', 'into', 'of', 'leaping']\n",
      "wish ['the', 'you', 'to', 'you', 'to', 'i', 'to']\n",
      "aware ['of', 'of', 'of', 'that', 'jekyll’s', 'that', 'of']\n",
      "thank ['you', 'you', 'you', 'you', 'you', 'god', 'you']\n",
      "maid ['servant', 'described', 'fainted', 'had', 'calls', 'had', 'lifted']\n",
      "besides ['were', 'was', 'for', 'a', 'with', 'with', 'which']\n",
      "observed ['the', 'utterson', 'with', 'the', 'that', 'that', 'that']\n",
      "among ['other', 'the', 'the', 'the', 'my', 'my', 'temptations']\n"
     ]
    }
   ],
   "source": [
    "# 使用这个单元格查找有多个后续单词，且至少有1个重复单词的双词组。\n",
    "\n",
    "def has_duplicates(t):\n",
    "    return len(set(t)) < len(t)\n",
    "\n",
    "for key, value in successor_map.items():\n",
    "    if len(value) == 7 and has_duplicates(value):\n",
    "        print(key, value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "e49d52f7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['east', 'in', 'to', 'to', 'up', 'to', 'of']"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "successor_map['going']"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b777a9c",
   "metadata": {},
   "source": [
    "在这个后续单词列表中，注意单词`'to'`出现了3次，其他后续单词只出现了1次。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8bf85fc",
   "metadata": {},
   "source": [
    "## 生成文本\n",
    "\n",
    "我们可以使用之前章节的结果，生成与原始文本关系相同的后续单词。\n",
    "\n",
    "以下是方法：\n",
    "\n",
    "- 以任意单词开始，我们查看可能的后续单词，并随机选取其中1个;\n",
    "- 然后，使用被选中的单词，我们查找可能的后续单词，随机选取1个。\n",
    "\n",
    "重复这个过程，生成我们想要的任意数量单词。例如，让我们以`'although'`开始，以下是可以跟随的单词："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "15108884",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['i', 'a', 'it', 'the', 'we', 'they', 'i']"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "word = 'although'\n",
    "successors = successor_map[word]\n",
    "successors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "747a41be",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "random.seed(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b26a2ead",
   "metadata": {},
   "source": [
    "我们可以使用`choice`按相同的概率选取列表中的单词。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "5a4682dc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'i'"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "word = random.choice(successors)\n",
    "word"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9741beca",
   "metadata": {},
   "source": [
    "如果相同单词出现过多次，它更有可能被选中。\n",
    "\n",
    "重复这些步骤，我们可以使用循环生成更长的句子。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "id": "36ee0f76",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "continue to hesitate and swallowed the smile withered from that "
     ]
    }
   ],
   "source": [
    "for i in range(10):\n",
    "    successors = successor_map[word]\n",
    "    word = random.choice(successors)\n",
    "    print(word, end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "38a2d79a",
   "metadata": {},
   "source": [
    "结果更像是一个真实的句子，但依然不是很合理。\n",
    "\n",
    "我们可以使用超过1个单词的元组作为`successor_map`的键。例如，我们可以创建一个字典，映射所有双词组或三词组后续的单词列表。\n",
    "\n",
    "作为练习，你将有机会实现这个分析过程，看看结果如何。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c59dff45",
   "metadata": {
    "tags": []
   },
   "source": [
    "## 调试\n",
    "\n",
    "目前我们编写了更实际性的程序，你可能会发现你花费了更多时间来调试。如果你被困难的问题卡住，以下是可以尝试的方法：\n",
    "\n",
    "- 阅读：检查你的代码，确认它写的与你想要写的一致;\n",
    "- 运行：修改并运行不同版本的代码，以进行实验。通常如果你在程序的正确位置显示了正确的结果，问题会变得明显，但有时你必须构建脚手架;\n",
    "- 琢磨：花些时间思考！该错误是哪种：语法，运行时或者语义错误？你能从错误信息或程序输出中获得什么信息？哪种错误可能导致你看到的问题？在问题出现之前你做的最后一个修改是什么？\n",
    "- 倾诉：如果你向其他人解释该问题，有时你会在结束询问之前自己找到答案。通常你不需要另一个人，你只需要与橡皮鸭对话。这就是著名的**橡皮鸭调试**策略。我不是在瞎编，你可以查看<https://en.wikipedia.org/wiki/Rubber_duck_debugging>;\n",
    "- 回退：有时，最好的方式是回退，撤销最近的修改，直到程序能够工作。然后你可以重新构建；\n",
    "- 休息：如果你让自己的大脑休息一下，有时它会为你找到答案。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12c2cd32",
   "metadata": {},
   "source": [
    "入门程序员有时会卡在一些方案中，忘记了其他方案。每种方案有对应的失败模式。\n",
    "\n",
    "例如，当代码中存在拼写错误时，阅读代码是有效的，但如果问题是概念错误则没有用。如果你不明白代码的含义，你可能阅读100次也无法看到错误，错误在你的脑中。\n",
    "\n",
    "进行小的简单测试可能有效。但如果你不进行思考或阅读代码，可能需要很长时间找出问题。\n",
    "\n",
    "你必须花时间思考。调试像是实验科学，你应该至少有一个假设，如果有多个可能，尝试进行测试，消除其中的一个可能。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a55036e1",
   "metadata": {},
   "source": [
    "但如果错误过多，或者代码太复杂，即使是最好的调试技术也会失败。有时最好的选项是回退代码，简化程序，直到回到可以基本运行的状态。\n",
    "\n",
    "新手程序员通常不愿意回退，因为他们无法忍受删除代码，即使代码是错误的。将你的代码复制到另一个文件后进行删减也许会让你好受点。然后你可以将代码片段逐步复制回来。\n",
    "\n",
    "寻找困难的故障需要阅读，运行，思考，回退，有时需要休息。如果你被某个步骤卡住，尝试其他步骤。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "25d091af",
   "metadata": {},
   "source": [
    "## 术语表\n",
    "- **默认值default value**：如果没有提供实参，将赋值给形参的值;\n",
    "- **覆盖override**：用实参替换默认值；\n",
    "- **决定论的deterministic**：决定论的程序在相同输入下每次运行结果都相同；\n",
    "- **伪随机pseudorandom**：伪随机的一组数看上去是随机的，但实际上由决定论的程序生成；\n",
    "- **双词组bigram**：两个元素的序列，元素通常是单词；\n",
    "- **三词组trigram**：三个元素的序列；\n",
    "- **n词组n-gram**：n个未定数量元素的序列；\n",
    "- **橡皮鸭调试rubber duck debugging**：向无生命对象解释问题的调试方法。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cde18229",
   "metadata": {},
   "source": [
    "## 练习"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "05752b6d",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Exception reporting mode: Verbose\n"
     ]
    }
   ],
   "source": [
    "# 这个单元格让Jupyter在出现运行时故障时提供更多调试信息。\n",
    "# 在进行练习前先运行本单元格。\n",
    "\n",
    "%xmode Verbose"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b0efab8",
   "metadata": {},
   "source": [
    "### 询问虚拟助手\n",
    "\n",
    "在`add_bigram`中，`if`语句根据字典中是否包含键来创建一个新的列表，或者在已有列表中追加元素。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "id": "a4365ac0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def add_bigram(bigram):\n",
    "    first, second = bigram\n",
    "    \n",
    "    if first not in successor_map:\n",
    "        successor_map[first] = [second]\n",
    "    else:\n",
    "        successor_map[first].append(second)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "30d9e549",
   "metadata": {},
   "source": [
    "字典提供`setdefault`方法，能够以更简洁的方法做相同的事。询问虚拟助手它的用法，或者复制`add_bigram`，询问能否用`setdefault`重写代码。\n",
    "\n",
    "本章我们实现了Markov链文本分析与生成。如果感到好奇，你可以询问虚拟助手更多关于该话题的信息。你可能知道，虚拟助手在许多方面使用相同的算法，但在重要的部分不相同。询问虚拟助手，“类似GPT的大语言模型与Markov链文本分析的区别在于？”"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "060c9ef6",
   "metadata": {},
   "source": [
    "### 练习\n",
    "\n",
    "编写计算每个3词组出现次数的函数。如果你用 _Dr. Jekyll and Mr. Hyde_ 文本测试函数，你应该得到最常用的3词组是“said the lawyer”。\n",
    "\n",
    "提示：参考`count_bigram`编写函数`count_trigram`。然后参考`process_word_bigram`编写函数`process_word_trigram`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f38a61ff",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 在这解答"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d047e546",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 在这解答"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ca1f8a79",
   "metadata": {
    "tags": []
   },
   "source": [
    "你可以使用以下循环读取这本书，然后处理单词。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "6b8932ee",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "trigram_counter = {}\n",
    "window = []\n",
    "\n",
    "for line in open(filename):\n",
    "    for word in split_line(line):\n",
    "        word = clean_word(word)\n",
    "        process_word_trigram(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "35d37fa1",
   "metadata": {
    "tags": []
   },
   "source": [
    "然后使用`print_most_common`寻找书中最常见的3词组。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "44c3f0d8",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "print_most_common(trigram_counter)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4bd07bb7",
   "metadata": {},
   "source": [
    "### 练习\n",
    "\n",
    "让我们实现Markov链文本分析，使用双词组到可能后继列表的映射。\n",
    "\n",
    "参考`add_bigram`，编写函数`add_trigram`，接受三词组列表，添加或者更新计数到`successor_map`中，使用前2个单词作为键，可能的第3个单词作为后继。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3fcf85f4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 在这解答"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "94d683fe",
   "metadata": {},
   "source": [
    "以下是调用`add_trigram`的`process_word_trigram`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "d9e554e3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def process_word_trigram(word):\n",
    "    window.append(word)\n",
    "    \n",
    "    if len(window) == 3:\n",
    "        add_trigram(window)\n",
    "        window.pop(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82eeed41",
   "metadata": {
    "tags": []
   },
   "source": [
    "你可以使用以下循环读取\"Eric, the Half a Bee\"歌词，测试函数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "8c2ee21c",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "successor_map = {}\n",
    "window = []\n",
    "\n",
    "for string in song.split():\n",
    "    word = string.strip(punctuation).lower()\n",
    "    process_word_trigram(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8829d4c2",
   "metadata": {
    "tags": []
   },
   "source": [
    "如果你的函数符合预期，`('half', 'a')`的后继为`['bee']`。实际上，这首歌的所有双词组只出现过1次，因此`successor_map`中对应的值也都只有单个元素。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "id": "b13384e3",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "successor_map"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "886212b5",
   "metadata": {},
   "source": [
    "你可以使用以下循环读取这本书，测试函数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "62c2177f",
   "metadata": {},
   "outputs": [],
   "source": [
    "successor_map = {}\n",
    "window = []\n",
    "\n",
    "for line in open(filename):\n",
    "    for word in split_line(line):\n",
    "        word = clean_word(word)\n",
    "        process_word_trigram(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e1d073e",
   "metadata": {},
   "source": [
    "在下一个练习中，你将使用这些结果生成新的随机文本。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04d7a6ee",
   "metadata": {},
   "source": [
    "### 练习"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "64e11f26",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# 初始化随机种子数，每次运行本书，它的结果相同。\n",
    "\n",
    "random.seed(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fb0f8f7d",
   "metadata": {},
   "source": [
    "要生成随机文本，我们将从`successor_map`随机选取键。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "fe2d93fa",
   "metadata": {},
   "outputs": [],
   "source": [
    "successors = list(successor_map)\n",
    "bigram = random.choice(successors)\n",
    "bigram"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83ed6c7e",
   "metadata": {},
   "source": [
    "现在编写循环，生成超过50个词：\n",
    "\n",
    "1. 寻找`successor_map`中可以跟随`bigram`的单词列表；\n",
    "2. 随机选择单词，将其打印；\n",
    "3. 在下一次迭代时，根据上次选取的单词创建新的双词组，然后选取后继词。\n",
    "\n",
    "例如，如果开始的双词组是`('doubted', 'if')`，选择的后继单词是`'from'`，那么下一个双词组是`('if', 'from')`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "22210a5c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 在这解答"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c71d8a89",
   "metadata": {},
   "source": [
    "如果每一步正确，生成的文本风格与原始文本类似，有些词组是合理的，但可能在多个话题之间游走。\n",
    "\n",
    "作为额外的练习，调整最后两个练习，使用`successor_map`中的三词组，查看这将如何影响结果。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3d4efda7",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "a7f4edf8",
   "metadata": {
    "tags": []
   },
   "source": [
    "[Think Python: 3rd Edition](https://allendowney.github.io/ThinkPython/index.html)\n",
    "\n",
    "Copyright 2024 [Allen B. Downey](https://allendowney.com)\n",
    "\n",
    "Code license: [MIT License](https://mit-license.org/)\n",
    "\n",
    "Text license: [Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-nc-sa/4.0/)"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Tags",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
